function BinaryTree() {
    var Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    // 根节点
    var root = null;

    // 插入root的子节点
    var insertNode = function(parentNode, newNode) {
        if (newNode.key < parentNode.key) {
            if (parentNode.left === null) {
                parentNode.left = newNode;
            } else {
                insertNode(parentNode.left, newNode)
            }
        } else {
            if (parentNode.right === null) {
                parentNode.right = newNode;
            } else {
                insertNode(parentNode.right, newNode)
            }
        }
    }
    // 先插入根节点
    this.insert = function(key) {
        var newNode = new Node(key);
        if (root == null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    };
    // 前序遍历
    var inOrderTraverseNode = function(node, callback) {
        // 判断当前不为null的话就访问左右子节点树
        if (node !== null) {
            // 访问左子树
            inOrderTraverseNode(node.left, callback);
            // 访问当前节点的key值
            callback(node.key);
            // 访问右子树
            inOrderTraverseNode(node.right, callback)
        }
    }

    this.inOrderTraverse = function(callback) {
        // 先从根节点遍历和每个节点的回调函数
        inOrderTraverseNode(root, callback)
    }
    // 前序遍历
    var preOrderTraverseNode = function(node, callback) {
        // 判断当前不为null的话就访问左右子节点树
        if (node !== null) {
            // 访问当前节点的key值
            callback(node.key);
            // 访问左子树
            preOrderTraverseNode(node.left, callback);
            // 访问右子树
            preOrderTraverseNode(node.right, callback)


        }
    }
    this.preOrderTraverse = function(callback) {
        // 先从根节点遍历和每个节点的回调函数
        preOrderTraverseNode(root, callback)
    }
    // 后续遍历
    var postOrderTraverseNode = function(node, callback) {
        // 判断当前不为null的话就访问左右子节点树
        if (node !== null) {
            // 访问当前节点的key值
            callback(node.key);
            // 访问左子树
            postOrderTraverseNode(node.left, callback);
            // 访问右子树
            postOrderTraverseNode(node.right, callback)
        }
    }
    this.postOrderTraverse = function(callback) {
        // 先从根节点遍历和每个节点的回调函数
        postOrderTraverseNode(root, callback)
    }
    //查找最小值
    this.getMinNum = function(node) {
        const minNode = node => {
            // 如果定义左子节点小于右子节点， 那就从左子节点找最小值
            return node ? (node.left ? minNode(node.left) : node.key) : null
        };
        return minNode(node || root)
    }
    //查找最大值
    this.getMaxNum = function(node) {
        const maxNode = node => {
            // 如果定义左子节点小于右子节点， 那就从左子节点找最小值
            return node ? (node.right ? maxNode(node.right) : node.key) : null
        };
        return maxNode(node || root)
    }
    //查找特定值
    this.getFindNum = function(data) {
        const findNode = (node, data) => {
            if (node === null) return false;
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                return findNode(node.left, data);
            } else if (data > node.key) { // 要查找的值大于当前节点的值，用右子树继续查找
                return findNode(node.right, data);
            } else {
                return true;
            }
        };
        return findNode(root, data)
    }
    //删除某节点值
    this.remove=function(data) {
        const removeNode = (node, data) => {
            if (node === null) return null; //如果不存在就返回null
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                node.left = removeNode(node.left, data);
                return node;
            } else if (data > node.key) {
                // 要查找的值大于当前节点的值，用右子树继续查找
                node.right = removeNode(node.right, data);
                return node;
            } else {
                if (node.left === null && node.right === null) return null;
                if (node.left === null) return node.right;
                if (node.right === null) return node.left;
                //在右子树中找到最小值节点
                var _node = this.getMinNum(node.right);
                // 将_node最小值节点的值更新为node最小值节点的值
                node.key = _node.key;
                // 因为最小值节点在右子树中 所以要从右子树中查找删除
                node.right = removeNode(node.right, node.key);
                // 然后返回节点
                return node;
            }
        };
        return removeNode(root, data)
    }

}

// var nodes = [16, 9, 15, 4, 16, 18, 14, 17, 24, 17, 28];
// var binaryTree = new BinaryTree();
// nodes.forEach(function(key) {
//     binaryTree.insert(key);
// });
//
// console.log("tree", binaryTree) //得到二叉树结构
// console.log(binaryTree.inOrderTraverse(callback)) //中序排列   【4, 9, 11, 14, 15, 16, 16, 17, 17, 17, 18, 24, 28 ]
// console.log(binaryTree.preOrderTraverse(callback)) //前序排列   [ 16, 9, 4, 15, 14, 11, 16, 18, 17, 17, 17, 24, 28 ]
// console.log(binaryTree.postOrderTraverse(callback)) //后序排列   [ 4, 11, 14, 15, 9, 17, 17, 17, 28, 24, 18, 16, 16 ]
// console.log(binaryTree.getMinNum()) //查找最小值   4
// console.log(binaryTree.getMaxNum()) //查找最大值  28
// console.log(binaryTree.getFindNum(12)) //查找最大值   false
// console.log(binaryTree.getFindNum(28)) //删除某值  节点 28
